package com.leetcode.algorithm.y21.m07;

/**
 * https://leetcode-cn.com/study-plan/algorithms/?progress=dqpwag
 * 第 2 天 双指针
 * 
 * @author jie.deng
 *
 */
public class Algorithms02 {

    /**
     * 977. 有序数组的平方
     * 
	 * 给定一个按非递减顺序排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。
	 * 
	 *  
	 * 
	 * 示例 1：
	 * 
	 * 输入：[-4,-1,0,3,10]
	 * 输出：[0,1,9,16,100]
	 * 示例 2：
	 * 
	 * 输入：[-7,-3,2,3,11]
	 * 输出：[4,9,9,49,121]
	 *  
	 * 
	 * 提示：
	 * 
	 * 1 <= nums.length <= 10000
	 * -10000 <= nums[i] <= 10000
	 * nums 已按非递减顺序排序。
     * @param nums
     * @return
     */
	public int[] sortedSquares(int[] nums) {
		int len = nums.length;
		int[] ret = new int[len];
		int retIdx = len - 1;
		if (nums.length == 0) {
			return ret;
		}
		int low = 0;
		int high = len - 1;
		while (low <= high) {
			int lowPow = nums[low] * nums[low];
			int highPow = nums[high] * nums[high];
			if (lowPow > highPow) {
				ret[retIdx] = lowPow;
				low++;
			} else {
				ret[retIdx] = highPow;
				high--;
			}
			retIdx--;
		}
		return ret;
	}
	
	
    /**
     * 189. 旋转数组 
     * 给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
     * 
     * 示例 1:
     * 输入: [1,2,3,4,5,6,7] 和 k = 3 
     * 输出: [5,6,7,1,2,3,4] 
     * 解释: 向右旋转 1 步: [7,1,2,3,4,5,6] 
     * 向右旋转 2 步: [6,7,1,2,3,4,5] 
     * 向右旋转 3 步: [5,6,7,1,2,3,4] 
     * 
     * 示例 2:
     * 输入: [-1,-100,3,99] 和 k = 2 
     * 输出: [3,99,-1,-100] 
     * 解释: 向右旋转 1 步: [99,-1,-100,3] 
     * 向右旋转 2 步: [3,99,-1,-100] 
     * 
     * 说明:
     * 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。 
     * 要求使用空间复杂度为 O(1) 的原地算法。
     * 
     * @param nums
     * @param k
     */
	public void rotate(int[] nums, int k) {
		int len = nums.length;
		if (len == 0) {
			return;
		}
		k = k % len;
		if (k == 0) {
			return;
		}
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
	}


	private void reverse(int[] nums, int start, int end) {
		while (start < end) {
			int tmp = nums[start];
			nums[start] = nums[end];
			nums[end] = tmp;
			start++;
			end--;
		}
	}	
}
